/**
 * 复写零
 *
 * 给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
 * 注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。
 *
 * 示例 1：
 * 输入：arr = [1,0,2,3,0,4,5,0]
 * 输出：[1,0,0,2,3,0,0,4]
 * 解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]
 *
 * 示例 2：
 * 输入：arr = [1,2,3]
 * 输出：[1,2,3]
 * 解释：调用函数后，输入的数组将被修改为：[1,2,3]
 *
 * 提示：
 * 1 <= arr.length <= 104
 * 0 <= arr[i] <= 9
 */

/**
 * 因为我们需要原地复写所有的零, 但是又因为是原地, 所以我们为了
 * 防止在复写的时候将前面的数给覆盖, 我们要从后面开始写起, 从后面
 * 开始写, 又因为数组的长度有限, 肯定是到达某个数字就结束了复写,
 * 所以我们要提前知道结束的数字是哪个数字, 那么我们可以用两个标志
 * 来标记最后复写的位置, 直到了复写结束的数字, 那我们就可以开始从
 * 后向前复写了
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(1)
 */

public class Main {
    public void duplicateZeros(int[] arr) {

        int n = arr.length;

        // 记录复写到哪里了 记录当前复写的数字
        // 初始化为 -1, 因为我们最后结束的位置要是 n - 1 或者 n
        int cur = -1, dest = -1;

        // 这里要注意 cur < n - 1
        // 因为我们这里用的是 ++dest, 要提前一个位置结束的, 不然数组的下标会越界
        while (cur < n - 1) {

            // 是 0, cur 要复写, 多加1
            if (arr[++dest] == 0) {
                cur++;
            }
            cur++;
        }

        // 这里提前判断一下, 不然会数组越界, 但是数组越界只有一种可能, 就是最后的
        // 位置遇到 0, 使 cur 多加了移动了一位, 所以会越界, 但是这个多加的位置是
        // 正好越界, 不用复写的, 所以我们特殊判断一下
        if (cur > n - 1) {
            cur --;
            dest--;
            arr[cur--] = 0;
        }

        // 这里就是正常的从结尾向前复写了
        while (dest >= 0) {
            if (arr[dest] == 0) {
                arr[cur--] = 0;
                arr[cur] = 0;
            } else {
                arr[cur] = arr[dest];
            }
            cur--;
            dest--;
        }
    }
}